#include "stdio.h"
#include <stdlib.h>
enum
{
    PRO = 1,
    BLKS,
    BLK,
    B,
    EPARAM,
    TYP,
    BASIC,
    POINTER,
    ARY,
    NUM,
    IDS,
    IDSS,
    EID,
    OPPARAM,
    PARAMS,
    PARAMSS,
    PARAM,
    PARY,
    SUB,
    DECL,
    STS,
    ST,
    ADDR,
    ASSIGN,
    ASSIGNOP,
    LOC,
    L,
    BOOL,
    BOLL,
    JOIN,
    JONN,
    EQUA,
    EQUAA,
    REL,
    RELL,
    EXPR,
    EXPRR,
    TERM,
    TERMM,
    UNARY,
    FACTOR
};
int VNEND = FACTOR;
enum
{
    INT = 60,
    CHAR,
    FLOAT,
    VOID,
    ASN,    // =
    SASN,   // +=
    MASN,   // -=
    AASN,   // *=
    DASN,   // /=
    MODASN, // %=
    LASN,   // <<=
    RASN,   // >>=
    EQU,    // ==
    NEQU,   // !=
    SUM,    // +
    MIN,    // -
    AST,    // *
    DIV,    // /
    MOD,    // %
    LMOV,   // <<
    RMOV,   // >>
    MOR,    // >
    LES,    // <
    NLES,   // >=
    NMOR,   // <=
    AND,    // &
    OR,     // |
    XOR,    // ^
    ANTI,   // ~
    NOT,    // !
    DAND,   // &&
    DOR,    // ||
    COMMA,  // ,
    LSQU,   // [
    RSQU,   // ]
    LBRA,   // (
    RBRA,   // )
    LCUR,   // {
    RCUR,   // }
    SEMI,   // ;
    ENUM,
    TRU,
    FAL,
    INTEGER,
    FLO,
    CHARACTER,
    STRING,
    ID,
    DOL, // $
    EMP
};
static int VTST = INT;
char VN[][20] = {"pro", "blks", "blk", "b", "eparam",
                 "typ", "bas", "ptr", "ary", "num", "ids",
                 "idss", "eid", "opp", "pams", "pams'", "pam",
                 "pary", "sub", "decl", "sts", "st", "addr",
                 "asn", "aop", "loc", "l", "bol", "boll", "jon", "jonn",
                 "equ", "equu", "rel", "rell", "exp", "expp", "tem", "temm",
                 "unary", "fac"};
char VT[][20] = {"int", "char", "float", "void",
                 "=", "+=", "-=", "*=", "/=", "%=", "<<=", ">>=", "==", "!=",
                 "+", "-", "*", "/", "%", "<<", ">>", ">", "<",
                 ">=", "<=", "&", "|", "^", "~", "!", "&&", "||",
                 ",", "[", "]", "(", ")", "{", "}", ";",
                 "enum", "true", "false", "integer", "float", "character", "string",
                 "id", "$"};
int productions[100][10] =
    {
        {PRO, BLKS}, //1
        {BLKS, BLK, BLKS},
        {BLKS, EMP},
        {BLK, TYP, ID, B},
        {BLK, ENUM, LCUR, EPARAM, RCUR, SEMI},
        {B, ARY, SEMI},
        {B, LBRA, OPPARAM, RBRA, LCUR, STS, RCUR},
        {TYP, BASIC, POINTER},
        {BASIC, VOID},
        {BASIC, CHAR},
        {BASIC, INT},
        {BASIC, FLOAT},
        {POINTER, AST},
        {POINTER, EMP},
        {EPARAM, IDS},
        {EPARAM, EMP},
        {IDS, EID, IDSS},
        {IDSS, COMMA, EID, IDSS},
        {EID, ID},
        {EID, ID, ASN, INTEGER},
        {ARY, LSQU, INTEGER, RSQU, ARY},
        {ARY, EMP},
        {NUM, INTEGER},
        {NUM, FLO},
        {OPPARAM, PARAMS},
        {OPPARAM, EMP},
        {PARAMS, PARAM, PARAMSS},
        {PARAMSS, COMMA, PARAM, PARAMSS},
        {PARAMSS, EMP},
        {PARAM, TYP, ID, PARY},
        {PARY, LSQU, SUB, RSQU, ARY},
        {PARY, EMP},
        {SUB, INTEGER},
        {SUB, EMP},
        {DECL, TYP, ID, ARY, SEMI},
        {STS, ST, STS},
        {STS, EMP},
        {ST, LCUR, STS, RCUR},
        {ST, DECL},
        {ST, ASSIGN},
        {ADDR, AND},
        {ADDR, EMP},
        {ASSIGN, POINTER, ID, ARY, ASSIGNOP, BOOL,SEMI},
        {ASSIGNOP, ASN},
        {ASSIGNOP, SASN},
        {ASSIGNOP, MASN},
        {ASSIGNOP, AASN},
        {ASSIGNOP, DASN},
        {ASSIGNOP, MODASN},
        {ASSIGNOP, LASN},
        {ASSIGNOP, RASN},
        {LOC, POINTER, ID, ARY},
        {LOC, ADDR, ID, ARY},
        {LOC, ADDR, L},
        {LOC, NUM},
        {LOC, CHARACTER},
        {L, ID, ARY},
        {L, STRING},
        {BOOL, JOIN, BOLL},
        {BOLL, DOR, JOIN, BOLL},
        {BOLL, EMP},
        {JOIN, EQUA, JONN},
        {JONN, DAND, EQUA, JONN},
        {JONN, EMP},
        {EQUA, REL, EQUAA},
        {EQUAA, EQU, REL, EQUAA},
        {EQUAA, NEQU, REL, EQUAA},
        {EQUAA, EMP},
        {REL, EXPR, RELL},
        {RELL, MOR, EXPR},
        {RELL, LES, EXPR},
        {RELL, NLES, EXPR},
        {RELL, NMOR, EXPR},
        {RELL, EMP},
        {EXPR, TERM, EXPRR},
        {EXPRR, SUM, TERM, EXPRR},
        {EXPRR, MIN, TERM, EXPRR},
        {EXPRR, EMP},
        {TERM, UNARY, TERMM},
        {TERMM, AST, UNARY, TERMM},
        {TERMM, DIV, UNARY, TERMM},
        {TERMM, EMP},
        {UNARY, NOT, UNARY},
        {UNARY, MIN, UNARY},
        {UNARY, FACTOR},
        {FACTOR, LBRA, BOOL, RBRA},
        {FACTOR, LOC},
        {FACTOR, NUM},
        {FACTOR, TRU},
        {FACTOR, FAL}};
int first[200][200];  //ÿһ�д���һ�����ս����ÿһ�д���һ���ս������0���Ǹ÷��ս����first�ĳ���
int follow[200][200]; //ÿһ�д���һ�����ս����ÿһ�д���һ���ս������0���Ǹ÷��ս����follow�ĳ���
int table[200][200];  //ÿһ�д���һ�����ս����ÿһ�д���һ���ս����[vn,vt]�洢��Ҫ������Լ�Ĳ���ʽ
int pi = 90, bias = 60;
int idx; //��ǰɨ��λ��
void printFirst();
void init()
{
    for (int i = VTST; i <= ID; i++)
    {
        first[i][i] = 1;
        first[i][0] = 1;
    }
}
void getFirst()
{
    int i, j;
    printf("\n%s\n", "GET First");
    int flag1 = 1, flag2;
    int vt, vn;
    while (flag1)
    {
        flag1 = 0;
        for (i = 0; i < pi; i++)
        {
            vn = productions[i][0];
            idx = 1;
            flag2 = 1;
            if (productions[i][idx] >= VTST)
            {
                vt = productions[i][idx];
                if (first[vn][vt] == 0)
                {
                    first[vn][vt] = 1;
                    first[vn][0]++;
                    flag1 = 1;
                }
            }
            else
            {
                while (flag2)
                {
                    flag2 = 0;
                    vt = productions[i][idx];
                    for (j = VTST; j <= ID; j++)
                    {
                        if (first[vt][j] == 1 && first[vn][j] == 0)
                        {
                            first[vn][j] = 1;
                            first[vn][0]++;
                            flag1 = 1;
                        }
                    }
                    if (first[vt][EMP] == 1)
                    {
                        if (productions[i][idx + 1] == 0)
                        {
                            if (first[vn][EMP] == 0)
                            {
                                first[vn][EMP] = 1;
                                first[vn][0]++;
                                flag1 = 1;
                                flag2 = 0;
                            }
                        }
                        else
                        {
                            idx++;
                            flag2 = 1;
                        }
                    }
                }
            }
        }
    }
}
void printFirst()
{
    int flag;
    for (int i = PRO; i <= VNEND; i++)
    {
        flag = 1;
        printf("first(%s)={", VN[i - 1]);
        for (int j = VTST; j <= ID; j++)
        {
            if (first[i][j] == 1)
            {
                if (flag)
                {
                    printf("%s", VT[j - bias]);
                    flag = 0;
                }
                else
                    printf(",%s", VT[j - bias]);
            }
        }
        if (first[i][EMP] == 1)
            printf(",@");
        printf("}\n");
    }
    printf("\n");
}
void getFollow()
{
    printf("%s\n", "GET Follow");
    int i, j, temp;
    int flag1 = 1;
    int vt, head;
    follow[PRO][DOL] = 1;
    while (flag1)
    {
        flag1 = 0;
        for (i = 0; i < pi; i++)
        {
            idx = 1;
            head = productions[i][0];
            while (productions[i][idx] != 0)
            {
                while (productions[i][idx] != 0 && productions[i][idx] >= VTST)
                    idx++;
                vt = productions[i][idx];
                if (productions[i][idx + 1] == 0)
                {
                    for (j = VTST; j <= DOL; j++)
                    {
                        if (follow[head][j] == 1 && follow[vt][j] == 0)
                        {
                            follow[vt][j] = 1;
                            flag1 = 1;
                        }
                    }
                }
                //A->aBb
                else
                {
                    temp = idx;
                    while (productions[i][temp + 1] != 0 && first[productions[i][temp + 1]][EMP] == 1)
                    {
                        for (j = VTST; j <= ID; j++)
                        {
                            if (first[productions[i][temp + 1]][j] == 1 && follow[vt][j] == 0)
                            {
                                follow[vt][j] = 1;
                                flag1 = 1;
                            }
                        }
                        temp++;
                    }
                    if (productions[i][temp + 1] == 0)
                    {
                        for (j = VTST; j <= DOL; j++)
                        {
                            if (follow[head][j] == 1 && follow[vt][j] == 0)
                            {
                                follow[vt][j] = 1;
                                flag1 = 1;
                            }
                        }
                    }
                    else
                    {
                        for (j = VTST; j <= ID; j++)
                        {
                            if (first[productions[i][temp + 1]][j] == 1 && follow[vt][j] == 0)
                            {
                                follow[vt][j] = 1;
                                flag1 = 1;
                            }
                        }
                    }
                }
                idx++;
            }
        }
    }
}
void printFollow()
{
    int flag;
    for (int i = PRO; i <= VNEND; i++)
    {
        flag = 1;
        printf("follow(%s)={", VN[i - 1]);
        for (int j = VTST; j <= DOL; j++)
        {
            if (follow[i][j] == 1)
            {
                if (flag)
                {
                    printf("%s", VT[j - bias]);
                    flag = 0;
                }
                else
                    printf(",%s", VT[j - bias]);
            }
        }
        printf("}\n");
    }
}
void getTable()
{
    printf("\nGET Table\n");
    int i, j;
    int vn, token;
    for (i = 0; i < pi; i++)
    {
        idx = 1;
        vn = productions[i][0];
        token = productions[i][idx];
        if (token == EMP)
        {
            for (j = VTST; j <= DOL; j++)
            {
                if (follow[vn][j] == 1)
                    table[vn][j] = i + 1;
            }
        }
        else
        {
            while (token != 0 && first[token][EMP] == 1)
            {
                for (j = VTST; j <= ID; j++)
                {
                    if (first[token][j] == 1)
                        table[vn][j] = i + 1;
                }
                token = productions[i][++idx];
            }

            if (token == 0)
            {
                for (j = VTST; j <= DOL; j++)
                {
                    if (follow[vn][j] == 1)
                        table[vn][j] = i + 1;
                }
            }
            else
            {
                for (j = VTST; j <= ID; j++)
                {
                    if (first[token][j] == 1)
                        table[vn][j] = i + 1;
                }
            }
        }
    }
}
void printProd(int i)
{
    idx = 1;
    printf("%s -> ", VN[productions[i][0] - 1]);
    while (productions[i][idx] != 0)
    {
        if (productions[i][idx] == EMP)
            printf("@");
        else if (productions[i][idx] >= VTST)
            printf("%s ", VT[productions[i][idx] - bias]);
        else
            printf("%s ", VN[productions[i][idx] - 1]);
        idx++;
    }
}
void printTable()
{
    printf("\t");
    int i, j;
    for (i = VTST; i <= DOL; i++)
        printf("%s\t", VT[i - bias]);
    printf("\n");
    for (i = PRO; i <= VNEND; i++)
    {
        printf("%s\t", VN[i - 1]);
        for (j = VTST; j <= DOL; j++)
        {
            if (table[i][j] > 0)
            {
                printf("%d", table[i][j] - 1);
            }
            printf("\t");
        }
        printf("\n");
    }
}
void output()
{
    FILE *fp;
    fp = fopen("pTable.txt", "w");
    if (fp == NULL)
    {
        printf("File open error!\n");
        exit(0);
    }
    fprintf(fp, "%d\n", pi);
    for (int i = 0, j; i < pi; i++)
    {
        j = 0;
        while (productions[i][j] != 0)
        {
            j++;
        }
        fprintf(fp, "%d", j);
        j = 0;
        while (productions[i][j] != 0)
        {
            fprintf(fp, " %d", productions[i][j]);
            j++;
        }
        fprintf(fp, "\n");
    }
    for (int i = PRO; i <= VNEND; i++)
    {
        for (int j = VTST; j <= DOL; j++)
        {
            if (table[i][j] > 0)
            {
                fprintf(fp, "%d %d %d\n", i, j, table[i][j]);
            }
        }
    }

    if (fclose(fp))
    {
        printf("can not close file!");
        exit(0);
    }
}
void printAllProd()
{
    for (int i = 0; i < pi; i++)
    {
        printf("%d: ", i + 1);
        printProd(i);
        printf("\n");
    }
}
int main()
{
    printAllProd();
    init();
    getFirst();
    printFirst();
    getFollow();
    printFollow();
    getTable();
    printTable();
    output();
    system("pause");
}